Communication networks are used to transport vast amounts of information. As more and more information is carried over these communication networks, the various communication devices (that is, network nodes), such as routers and switches, are called upon to process still increasing amounts of data traffic. Often times, the data traffic includes data having different bandwidth requirements. The data traffic may also have different priority levels. On the output side of a communication device, memory buffers are used to store data units when traffic bursts cause data units to be received at a communication device at a faster rate than they can be processed. The various communication devices within a communication network must schedule data transmissions for the data units based upon, among other things, the relative bandwidth requirements of the data. Many traffic control techniques have been developed in conjunction with memory buffers to schedule data units for transmission. Data units may be portions of packets, frames, cells, or other units of data.
Communication links between network nodes in packet-based communications networks are often referred to as “interfaces.” An interface can be a physical entity (for example, a port or a switch or router) or a logical entity (for example, a channel in a packet over a SONET (POS) link, a VC, or a VLAN). An example of when many channels, VCs, or VLANs run over a single physical circuit can be found in packet or cell switching, in which packets from many sources are multiplexed and transmitted from endpoint to endpoint over a switched network.
Typical output traffic control implementations have included one or more queues per interface to buffer output traffic. In many products, such queues are built into hardware for efficiency. However, newer and more advanced communication devices may be called on to handle thousands of interfaces, wherein different interfaces may support different traffic types and may have different bandwidth requirements. Hardware required to support each interface combination in a communication device is inflexible with respect to the number or queues, enqueue properties, and dequeue properties, for example. Accordingly, each hardware implementation is typically custom designed for that interface combination. Custom designing hardware for each particular interface combination is a costly and time consuming task.
Software-based queuing provides much more flexibility. However, the standard methods of interface scheduling and traffic control in software do not scale up well (that is, do not perform well) for large numbers of interfaces, especially on high-speed lines. Accordingly, there is a need in the art for efficient software-based interface scheduling for large numbers of interfaces.